public class code01 {
//    力扣 150 组合
// 首先第一步，理解题目
// 这里的 n 代表的是当前数字的范围
// k 表示的是当前返回 数组对 中，一个数组的长度以及包含的元素个数
// 可以看到题目中的输入为 4， 2
// 答案的规律就是 [1,2]、[1,3]、[1,4]、[2,3]、[2,4]、[3,4]
public List<List<Integer>> combine(int n, int k) {
    // 首先创建出一个顺序表，用来存储返回值
    List<List<Integer>> re = new ArrayList<>();

    // 判断特殊情况
    if(k <=0 || n < k) {
        // 此时直接返回一个空数组即可
        return re;
    }

    // 创建一个双端队列，用来存储当前 k 个元素并进行存储
    Deque<Integer> que = new ArrayDeque<>();
    // 创建一个方法，通过递归的形式将值获取并且存储起来
    dfs(n, k, 1, que, re);

    return re;
}

    // 实现这里的核心方法
    // 在这里的方法中需要设定如下的参数实现递归
    // n 和 k
    // 当前起始位置的值
    // 双端队列和返回数组
    private void dfs(int n, int k, int start, Deque<Integer> que, List<List<Integer>> re) {
        // 首先设置递归返回条件
        if(que.size() == k) {
            // 当出现队列中存储的值的数量和要求的 k 的长度相同。
            // 此时就需要将队列中的值存储到返回链表中
            // 并且返回到上一层的递归
            re.add(new ArrayList<>(que));
            return;
        }

        // 在这里需要实现的是递归的核心代码
        // 从 start 开始，通过 for 循环来找到需要的值
        for(int i = start; i <= n; i++) {
            // 从尾部向双端队列中插入值
            que.addLast(i);
            // 进行下一轮的递归，此时 需要更新新的搜索起始点，因为题目要求不能出现重复元素
            dfs(n, k, i+1, que, re);
            // 递归返回后，就会执行到下面的代码
            // 因为是队列中的元素不会超过 2 个
            // 此时就需要将队列尾部的最后一个值移除即可
            que.removeLast();
        }
    }
}
